import java.util.LinkedList;
import java.util.Random;
/*
 * 最随机的应该是
 */
public class RandomQueue<E>{ 

    private LinkedList<E> queue;

    public RandomQueue(){
        queue = new LinkedList<E>();
    }

    public int add(E e){
        if(Math.random() < 0.5) {
        	queue.addFirst(e);
        	return 0;
        }
        else {
        	queue.addLast(e);
        	return size()-1;
        }
    }
    
    public void add_(E e){
    	if(new Random().nextDouble() < 0.88) {
    		if(new Random().nextDouble() < 0.5)
    			queue.addFirst(e);
    		else
    			queue.addLast(e);
    	}
    	else
    		addInside(e);
    }
    
    public void addInside(E e) {
    	if(size() == 0 || size() == 1 || size() == 2) add(e);
    	else	
    		queue.add(new Random().nextInt(size()-2)+1, e);   //[1-size)
//    		queue.add(new Random().nextInt(size()), e);   //[1-size)
    }
    
    public void addFirst(E e) {
		queue.addFirst(e);
	}
   
    public E remove(){
        if(queue.size() == 0)
            throw new IllegalArgumentException("There's no element to remove in Random Queue");

        if(new Random().nextDouble() < 0.5)
            return queue.removeFirst();
        else
            return queue.removeLast();
    }
    
    public E remove_(){
        if(queue.size() == 0)
            throw new IllegalArgumentException("There's no element to remove in Random Queue");
        if(new Random().nextDouble() < 0.88) {
        	if(new Random().nextDouble() < 0.5)
        		return queue.removeFirst();
        	else
        		return queue.removeLast();
        }
        else
        	return removeInside();
    }
    
    public E removeInside() {
		if(size() == 0 || size() == 1 || size() == 2) return remove();
		else
			return queue.remove(new Random().nextInt(size()-2)+1);
	}
    

    public int size(){
        return queue.size();
    }

    public boolean empty(){
        return size() == 0;
    }
}